package com.leecode;

import java.util.HashMap;

public class Leet64 {
	public static void main(String[] args) {
		new Leet64().minPathSum(new int[][]
			   {{5, 0, 1, 1, 2, 1, 0, 1, 3, 6, 3, 0, 7, 3, 3, 3, 1},
				{1, 4, 1, 8, 5, 5, 5, 6, 8, 7, 0, 4, 3, 9, 9, 6, 0},
				{2, 8, 3, 3, 1, 6, 1, 4, 9, 0, 9, 2, 3, 3, 3, 8, 4},
				{3, 5, 1, 9, 3, 0, 8, 3, 4, 3, 4, 6, 9, 6, 8, 9, 9},
				{3, 0, 7, 4, 6, 6, 4, 6, 8, 8, 9, 3, 8, 3, 9, 3, 4},
				{8, 8, 6, 8, 3, 3, 1, 7, 9, 3, 3, 9, 2, 4, 3, 5, 1},
				{7, 1, 0, 4, 7, 8, 4, 6, 4, 2, 1, 3, 7, 8, 3, 5, 4},
				{3, 0, 9, 6, 7, 8, 9, 2, 0, 4, 6, 3, 9, 7, 2, 0, 7},
				{8, 0, 8, 2, 6, 4, 4, 0, 9, 3, 8, 4, 0, 4, 7, 0, 4},
				{3, 7, 4, 5, 9, 4, 9, 7, 9, 8, 7, 4, 0, 4, 2, 0, 4},
				{5, 9, 0, 1, 9, 1, 5, 9, 5, 5, 3, 4, 6, 9, 8, 5, 6},
				{5, 7, 2, 4, 4, 4, 2, 1, 8, 4, 8, 0, 5, 4, 7, 4, 7},
				{9, 5, 8, 6, 4, 4, 3, 9, 8, 1, 1, 8, 7, 7, 3, 6, 9},
				{7, 2, 3, 1, 6, 3, 6, 6, 6, 3, 2, 3, 9, 9, 4, 4, 8}}
		);
	}

	public int minPathSum(int[][] grid) {
		return dp(grid, 0, 0);
	}

	/**
	 * 你看看当时不会dp的时候写的有多sb
	 */
	HashMap<String, Integer> map = new HashMap();
	int count = 0;
	public int dp(int[][] grid, int x, int y) {
		if (x == grid.length - 1 && y == grid[x].length - 1) return grid[x][y];

		if (x == grid.length - 1) {
			if (map.containsKey("" + x + "" + y))
				return map.get("" + x + "" + y);
			int res = grid[x][y] + dp(grid, x, y + 1);
			map.put("" + x + "" + y, res);
			return res;
		}
		if (y == grid[x].length - 1) {
			if (map.containsKey("" + x + "" + y))
				return map.get("" + x + "" + y);
			int res2 = grid[x][y] + dp(grid, x + 1, y);
			map.put("" + x + "" + y, res2);
			return res2;
		}

		if (map.containsKey("" + x + "" + y))
			return map.get("" + x + "" + y);
//		int res3=Math.min(grid[x][y]+dp(grid,x+1,y),grid[x][y]+dp(grid,x,y+1));
		int res3;
		if (grid[x][y] + dp(grid, x + 1, y) < grid[x][y] + dp(grid, x, y + 1)) {
			res3 = grid[x][y] + dp(grid, x + 1, y);
			System.out.println(count + grid[x][y]);
			System.out.println(grid[x][y] + "->" + grid[x + 1][y]);
		} else {
			res3 = grid[x][y] + dp(grid, x, y + 1);
			System.out.println(count + grid[x][y]);
			System.out.println(grid[x][y] + "->"+grid[x][y + 1]);
		}
		map.put("" + x + "" + y, res3);
		return res3;
	}

	/**
	 * 87%,94%,自创,学会dp后的第一遍
	 */
	public int minPathSum2(int[][] grid) {
		int lines=grid.length;
		int colum=grid[0].length;
		for (int a = 1; a < colum; a++) {
			grid[0][a]+=grid[0][a-1];
		}
		for (int a = 1; a < lines; a++) {
			grid[a][0]+=grid[a-1][0];
		}

		for (int b = 1; b < lines; b++) {
			for (int a = 1; a < colum; a++) {
				grid[b][a]+=Math.min(grid[b][a-1],grid[b-1][a]);
			}
		}

		return grid[lines-1][colum-1];
	}
}
